package org.b3log.exercise.trains;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

/**
 * Route resolver.
 *
 * @author <a href="mailto:DL88250@gmail.com">Liang Ding</a>
 * @version 1.0.0.1, Mar 16, 2011
 */
public final class RouteResolver {

    /**
     * Indicates no such route, specified value is {@value #NO_SUCH_ROUTE}.
     */
    private static final int NO_SUCH_ROUTE = -1;
    /**
     * Graph to resolve.
     */
    private Graph graph;
    /**
     * Count maximum stops(less than).
     */
    private int maxStopsCount = 0;
    /**
     * Route count mode.
     */
    private RouteCountMode routeCountMode;
    /**
     * Route stack. Holds the name of visited node.
     */
    private Stack<String> routeStack = new Stack<String>();
    /**
     * Maximum distance.
     */
    private int maxDistance;
    /**
     * Starting node.
     */
    private Node startingNode;
    /**
     * Ending node.
     */
    private Node endingNode;
    /**
     * Valid routes: distance=route.
     * For example "A-B-C"=12.
     */
    private Map<String, Integer> routes;

    /**
     * Constructs a route resolver with the specified graph.
     *
     * @param graph the specified graph
     */
    public RouteResolver(final Graph graph) {
        this.graph = graph;
    }

    /**
     * Gets routes with the specified starting node name, ending node
     * name, maximum stops count, route count mode and maximum distance.
     *
     * <p>
     * The returned routes contain all paths from the specified starting node to
     * the ending node, including circling routes if the graph contains circles.
     * Use the specified maximum stops count or maximum distance to jump out
     * (backtrack) from these circles.
     * </p>
     *
     * @param startingNodeName the specified starting node name
     * @param endingNodeName the specified ending node name
     * @param maxStopsCount the specified maximum stops count
     * @param routeCountMode the specified route count mode
     * @param maxDistance the specified maximum distance
     * @return a map of routes, for example {11="C-E-B-C", 18="C-D-C-D-C", ....}
     * @see #resolve(org.b3log.exercise.trains.Node) 
     */
    public Map<String, Integer> getRoutes(final String startingNodeName,
            final String endingNodeName,
            final int maxStopsCount,
            final RouteCountMode routeCountMode,
            final int maxDistance) {
        startingNode = graph.getNode(startingNodeName);
        endingNode = graph.getNode(endingNodeName);
        this.maxStopsCount = maxStopsCount;
        this.routeCountMode = routeCountMode;
        this.maxDistance = maxDistance;
        this.routes = new HashMap<String, Integer>();

        final Set<Node> destinations = startingNode.getDestinations();

        for (final Node destination : destinations) {
            resolve(destination);
        }

        return Collections.unmodifiableMap(routes);
    }

    /**
     * Gets distance for the specified route description.
     *
     * @param route the specified route description, for example,
     * {@literal A-B-C} represents start at A, then travel directly to B, then
     * directly to C.<br/>
     * A, B, C represents names of three {@link Node node}s, respectively.
     * @return distance of the specified route, returns "NO_SUCH_ROUTE"
     * if no such route
     */
    public String getDistance(final String route) {
        final int distance = calcDistance(route);

        if (NO_SUCH_ROUTE == distance) {
            return "NO SUCH ROUTE";
        } else {
            return String.valueOf(distance);
        }
    }

    /**
     * Traverses a graph with the specified destination node by deep traversal.
     *
     * <p>
     * The traversal contains circling routes(if the graph contains circles),
     * backtrack if the distance of the current route greater than the given
     * {@linkplain #maxDistance maximum distance} or {@linkplain #maxStopsCount
     * maximum stops count}.
     * </p>
     *
     * @param destNode the specified destination node
     */
    private void resolve(final Node destNode) {
        routeStack.push(destNode.getName());
        final int stopsCnt = routeStack.size();

        if (stopsCnt > maxStopsCount) {
            routeStack.pop(); // backtrack
            return;
        }

        if (destNode.equals(endingNode)) { // found a route
            boolean match = false;

            switch (routeCountMode) {
                case EQUAL_STOP_COUNT:
                    if (maxStopsCount == stopsCnt) {
                        match = true;
                    }
                    break;
                case LESS_OR_EQUAL_STOP_COUNT:
                    if (stopsCnt <= maxStopsCount) {
                        match = true;
                    }
                    break;
                default:
                    throw new RuntimeException("Unspecified rounte count mode");
            }

            if (match) {
                final String route = getCurrentRoute();
                final int distance = calcDistance(route);

                if (distance > maxDistance) {
                    routeStack.pop(); // backtrack
                    return;
                } else {
                    routes.put(route, distance); // save the route
                }
            }
        }

        for (final Node destination : destNode.getDestinations()) {
            resolve(destination);
        }

        routeStack.pop(); // backtrack
    }

    /**
     * Calculates the distance with the specified route.
     *
     * @param route the specified route
     * @return distance, returns {@value #NO_SUCH_ROUTE} if no such route
     */
    private int calcDistance(final String route) {
        final String[] nodeNames = route.split("-");

        int ret = 0;
        for (int i = 0; i < nodeNames.length; i++) {
            final String nodeName = nodeNames[i];
            final Node node = graph.getNode(nodeName);

            if (i + 1 < nodeNames.length) {
                final Node nextNode = graph.getNode(nodeNames[i + 1]);
                if (null == nextNode) {
                    return NO_SUCH_ROUTE;
                }

                final int distance = node.getDistance(nextNode);
                if (0 == distance) {
                    return NO_SUCH_ROUTE;
                }

                ret += distance;
            }
        }

        return ret;
    }

    /**
     * Gets the current route description from {@linkplain #routeStack
     * route stack}.
     *
     * @return route, for example "A-B-C"
     */
    private String getCurrentRoute() {
        final StringBuilder routeBuilder =
                new StringBuilder(startingNode.getName() + '-');
        for (int i = 0; i < routeStack.size(); i++) {
            final String nodeName = routeStack.elementAt(i);
            routeBuilder.append(nodeName);

            if (i < routeStack.size() - 1) {
                routeBuilder.append('-');
            }
        }

        final String ret = routeBuilder.toString();

        return ret;
    }

    /**
     * This enumeration defines all route calculating modes by stops count.
     *
     * @author <a href="mailto:DL88250@gmail.com">Liang Ding</a>
     * @version 1.0.0.0, Mar 15, 2011
     */
    public static enum RouteCountMode {

        /**
         * Indicates sums route count if count of stops of the route
         * less or equal than the specified stop count.
         */
        LESS_OR_EQUAL_STOP_COUNT,
        /**
         * Indicates sums route count if count of stops of the rout exactly
         * equals to the specified stop count.
         */
        EQUAL_STOP_COUNT;
    }
}
